C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_100/193_01/crypt.doc

Text File | 1985-11-13 | 17KB | 334 lines

12/9/85
INTRODUCTION

The "Infinite Key Encryption System" article in issue #94 (August
1984)  of Dr.  Dobbs contains an excellent tutorial on Encryption
Systems.  At  the  time it was published,  I read  it  with  only
passing  interest.  About six months ago,  I developed a need for
this type of utility and so begins my story.  The  first thing  I
did was write a shell cypher program (cypher.c-Listing #1). Since
I  had already written a generic file copy utility which  allowed
modifications  during transfer,  it was a simple matter to modify
the argument passing to include multiple keys and add a  cypher()
function  call to encrypt the file with a simple exclusive-or'ing
algorithm (cypher1.c-Listing #2).  While this method did  encrypt
the  file  and  allowed for easy decryption (using the  same  run
string),   there   were  definite   detectable  patterns  in  the
resultant  file.  These patterns,  a function of the key  period,
were  easily found in areas of repetitive  characters.  (  eg.  a
string of asterisks or spaces, the hex 1A's at the end of a file,
etc  )  Another drawback to this scheme is the inability to  pass
nonprintable  characters in the runstring,  thereby limiting  the
number  of encryption tokens.  Sooooo it was back to the  drawing
board.

Rereading  the aforementioned article with  renewed  interest,  I
gained  an  insight  into the methods and  schemes  of  practical
modern  cyphers.  I don't intend to cover these concepts,  so  if
you're  interested  or lacking in the basics,  avail yourself  of
that article, and those in its  bibliography.

While the tutorial portion was excellent,  I disagreed with a few
points on implementation.  First,  there was the code itself  and
the intimation that assembly language was required for reasonable
speed.  The  MAC Assembler is only used with CP/M-80 and I wanted
more portable source,  so I decided to write it in C.  Second,  I
felt  that a random key  of some prime length could be  generated
solely from the original key (cypher2.c - Listing  #3).  Although
some  keys  may  work better than others,  a  means  to  evaluate
results  can  render this method very  functional.  And  last,  I
disagreed  with the need for passing information in the encrypted
file.  It  seemed  unnecessary and cumbersome.  My  goal  was  to
develop  a  method  that  worked entirely  from  the  run-string.
Overall  I  must commend the work done by John  Thomas  and  Joan
Thersites  for  presenting  such a complete  treatment  of  thier
topic.


THE ULTIMATE CYPHER

The  ultimate cypher is like the ultimate weapon.  No matter  how
sophisticated,  an  anti-weapon  (anti-cypher) can eventually  be
developed, IF there is a need. The user must make some judgements
regarding  needs  and  level  of  protection.  The  2  algorithms
mentioned  are relatively simple to implement and use.  The  same
keys  will  encypher  or decypher the file and  key  order  isn't
important.  The experts (and it becomes quite obvious) point  out
that  the  strongest  cypher  schemes utilize  a  combination  of
transposition and substitution.  However,  when  transposition is
added,  the  order  of decyphering must be the exact  reverse  of
encyphering.  The  last cypher  module contains an algorithm  for
transposing  the file tokens along with the random generated  key
encryption scheme (cypher3.c-Listing #4).  This is a small  price
to pay for the added security.


THE NEED FOR TOOLS

As  I  progressed in my quest of the   ultimate   cypher/decypher
algorithm,  I  became  aware of the deficiencies of the  standard
CP/M utilities at my disposal, so I developed my own.

The first tool,  fv.c (file view - Listing #5),  replaced my CP/M
dump.com.  Dump provides a continual display on screen of the hex
contents of a file.   Since most encryption is performed on  text
files, it is most beneficial to include the ascii form along with
the  hex.  And,  since most algorithms use an exclusive-or as the
means of encryption it was easy enough to dump two files and  the
exclusive-ored difference between them.

The next tool,  fstat.c (file statistics - Listing #6) calculates
and  display  the statistical characteristics of the  file.  This
tool scans the file, counting the occurances of each element, and
provides a 16 x 16 display of the distribution of characters.  It
calculates  mean,   median,  mode  and  range  of  the  character
distribution and displays it's histogram.  As one might  suspect,
each  file type  has a definite signature.  In fact after limited
use  of  this  utility the user will be  able  to  recognize  the
histogram patterns for text, Wordstar, and many other files.

While experimenting with various schemes, it becomes obvious that
the most difficult file to disguise is one that contains a single
byte for every entry or some sequential scheme.  So the next task
was  developing a utility,  makef.c (make file - Listing #7),  to
generate  a known sequential or uni-character file of  some  user
defined length.

Finally the last utility,  sp.c (search pattern - Listing #7),  I
needed  was  a  search scheme to look  for  repetitive   patterns
occuring  within  a file and provide some  information  regarding
location and depth of the repetition. Also included is the option
to   calculate the delta characteristics of a file to search  for
repetitive mathematical as well character sequences.


CYPHER.C - LISTING #1

The cypher shell program is provided for use as is,  or for  user
modification.  It contains the argument passing and file handling
source  code  needed to copy from an existing file to a new  file
via  a  16 Kbyte buffer with a cypher function  being  called  to
encrypt  the  file (If the file is less than 16k the  input  file
name  may be the same as the output thus destroying the  original
contents)  A  16K buffer was chosen because it should fit  easily
with  most  compilers.   This  value  may  be  adjusted  to  meet
individual  compiler needs.  Any of the 3 algorithms that  follow
may be included or linked with this shell. Caution is recommended
to  ensure that the function name is appropriate for  the  method
you  use.  The  keys  are  passed in the CP/M  command  line  and
therefore  limited by its length as well as the argument  passing
capability of the C-compiler.


CYPHER1.C - LISTING #2

This minimal cypher algorithm uses an exclusive-or'ing scheme  to
encrypt  the file with the keys passed.  If the user employs keys
of some prime length and performs multiple passes the results can
be  quite difficult to decypher.  It's quick and easy to use  and
provides  an excellent means to test the basics of  cryptography.
Since the keys are limited to only include printable  characters,
we  don't  take full advantage of the 256 codes available  for  a
byte.

CYPHER2.C - LISTING #3

Now  something a little more difficult for the code  breaker,  an
algorithm  which grew out of the previous listing and generates a
prime length key for each user key passed. One of 50 prime values
(betweem  1009  and 1999) is selected as a function  of  the  key
passed.  The  prime key is then generated using a simple summing-
anding-exclusive oring algorithm and the file is encrypted  using
this  new  key.  If  two  or more  keys  are  used,  this  method
guarantees  a  cypher  period in excess of  1,000,000,  which  is
significantly larger than most text files.

The  key generation scheme is based entirely on the original  key
length  and its contents and I fail to see how this can be worked
backwards to regain the original, especially if multiple keys are
used.  Some  keys will generate shorter periods within the  prime
length,  but  this is easily tested with the  tools  provided.  I
welcome feedback or suggestions for improving this algorithm.


CYPHER3.C - LISTING #4

Adding  chaos to disorder has probably driven many a code-cracker
to drink.  And this is just what w